1. Field of the Invention
The present invention relates generally to selecting a set of satellites for tracking and navigation, and more particularly, to a satellite navigational system receiver selecting an optimum subset of tracking satellites from one or more satellite navigational system constellations.
2. Description of the Related Art
Satellite navigational systems provide positional information, normally geo-spatial, to earth-bound receivers. Each system has its own constellation of satellites orbiting the Earth, and, in order to calculate its position, a receiver in that system uses the satellites “in view” (i.e., in the sky above) of that system's constellation. Generally, the larger the number of satellites in view, the more accurate the calculation of the receiver's position will be. Global Navigational Satellite Systems (GNSS) is often used as the generic term for such systems, even though such navigational satellite systems include, e.g., regional and augmented systems—i.e., systems that are not truly “global.” The term “GNSS,” as used herein, covers any type of navigational satellite system, global or not, unless expressly indicated otherwise.
As the electronics for GNSS receivers have gotten smaller, and the positional calculations have become more accurate, the use of GNSS functions has become ubiquitous in consumer and other electronic devices, from cellular telephones to automobiles. And, as the number of uses for GNSS receivers has grown substantially and is still growing, the number of GNSS systems, both planned and presently operational, is also growing. The widely-known, widely-used, and truly global Global Positioning System (GPS) has been joined by one other global system, the GLObalnaya NAvigatsionnaya Sputnikovaya Sistema (GLONASS), and will be joined by the Galileo and COMPASS systems—each of which has, or will have, its own constellation of satellites orbiting the globe. Regional systems (those that are not global, but intended to cover only a certain region of the globe) include the Quasi-Zenith Satellite System (QZSS) and the Indian Regional Navigational Satellite System (IRNSS) currently being developed. Augmented systems (which are normally regional as well, and which “augment” with, e.g., messages from ground-based stations and/or additional navigational aids) include Wide Area Augmentation System (WAAS), European Geostationary Navigation Overlay Service (EGNOS), Multi-functional Satellite Augmentation System (MSAS), and GPS Aided Geo Augmented Navigation (GAGAN).
Since a GNSS receiver may be configured to use satellites from multiple GNSS systems, the ever-expanding number of GNSS constellations means an ever-increasing accuracy of positional calculation for GNSS receivers. However, there is a downside to a GNSS receiver using “too many” satellites for positional calculation because, after a certain number of satellites, the beneficial increase in accuracy is greatly outweighed by the detrimental increase in resources needed for tracking, receiving input, and doing the necessary processing for calculating the GNSS receiver's position based on the larger number of satellites.
The accuracy of a GNSS receiver may be understood in terms of Dilution of Precision (DOP). The various computations and “flavors” of DOP, such as geometrical DOP (GDOP), positional DOP (PDOP), horizontal DOP (HDOP), vertical DOP (VDOP), and time DOP (TDOP), are well-known to one of ordinary skill in the art, but the problem being measured by DOP may be simply described by the two dimensional analogy shown in FIG. 1. A receiver in FIG. 1 is using two radio transmitters to calculate its position. In (a), the two transmitters are almost at right angles to the receiver (“orthogonal”), which means their radio signals are also almost orthogonal to each other when received by the receiver in the overlapped zone at the center. In (b), the two transmitters are closer together, and the region where their signals overlap over the receiver is much wider and more diffuse. Thus, the positional DOP (PDOP) of the receiver using the two transmitters in (b) is high, while the PDOP of the receiver using the two transmitters in (a) is low. Simply put, the more orthogonal the signals, the lower the DOP.
A helpful way to view the problem of DOP in three dimensions is to consider the volume of the polyhedron formed by drawing lines between the GNSS receiver and each of the satellites being tracked. For example, in FIG. 2 (which is based upon a drawing in R. Langley, “Dilution of Precision,” GPS World, May 1999, which is hereby incorporated by reference in its entirety), there are 4 satellite points 210, 220, 230, and 240 in the “sky,” represented by the globe, and a GNSS receiver point 200 on the “ground,” at the center of the globe. Drawing lines between GNSS receiver point 200 and all satellite points 210, 220, 230, and 240, as well as between contiguous satellite points 210, 220, 230, and 240, forms the tetrahedron shown in FIG. 2. The volume of that tetrahedron is highly correlated with the Geometric DOP (GDOP) of the GNSS receiver when using those four satellites. Thus, if one or more of the satellite points 220, 230, and 240 closer to the horizon (i.e., at the bottom of the tetrahedron) are moved closer to the satellite point 210 near the zenith (i.e., at the top of the tetrahedron), the volume of the tetrahedron would decrease, and the GDOP of the GNSS receiver using those four satellites would increase.
To consider the problem of increase in accuracy (i.e., decrease in DOP) based on having a larger number of satellites vs. the increase in resources for using that larger number of satellites, consider that a typical GNSS receiver may have 20 satellites in view at any point in time. The horizontal DOP (HDOP) for that GNSS receiver using all 20 satellites in view may be around 0.6, while using only 12 of those satellites provides an HDOP of 0.8. The decrease in HDOP when using 20 instead of 12 is minimal compared to, e.g., the amount of extra power and/or computing resources needed to track, process input, and calculate the GNSS receiver's location using those 8 additional satellites. Depending on the specific implementation and system involved, using only 12 satellites rather than all 20 may result in a nearly 50% power savings.
Thus, there are benefits for a GNSS receiver to select a subset of the total number of satellites in view for purposes of efficiently performing positional processing and calculation. However, the selection of that subset can be computationally expensive—i.e., quite a waste of resources in and of itself. Consider the following equation for calculating the number of different possible subsets of N satellites out of M total satellites in view:
                              (                                                    M                                                                    N                                              )                =                                            M              ⁡                              (                                  M                  -                  1                                )                                      ⁢                          (                              M                -                2                            )                        ⁢                                                  ⁢            …            ⁢                                                  ⁢                          (                              M                -                N                +                1                            )                                            N            !                                              (        1        )            
Using this equation, we find that, for M=20 satellites in view, there are 125,970 different possible subsets of N=12 satellites from which the optimal tracking subset must be selected.
Currently, GNSS receivers use recursive algorithms to determine the subset/combination of satellites with the optimum DOP out of all of the possible subsets/combinations of N satellites from the M in view. This is a computationally burdensome task for a GNSS receiver, a burden which will continue to grow into the future, as new constellations of satellites go online (creating ever-larger Ms to choose from), the electronics (and available resources) for GNSS receivers continue to shrink, the usage and integration of GNSS receivers into other systems and devices grows, etc.
Thus, a solution is needed for a GNSS receiver to select an optimum tracking subset of satellites in view without burdensome calculations, such as, e.g., recursive DOP algorithms.